The present invention relates generally to real time applications and more specifically to a network scheduler for such applications.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawings hereto: Copyright(copyright) 1998, 1999 Honeywell, Inc., All Rights Reserved.
Real time systems comprise programs that must execute relative to priorities or within strict constraints on response time. Some examples of real-time systems include industrial plant controllers, medical monitors, communications networks, and aircraft or spacecraft flight control systems. One difficulty in designing real-time systems is in the strict requirement to meet processing deadlines and not in the actual speed of processing. A real-time system need not be complex or high performance. Checking radioactivity levels in a nuclear power plant or checking a pulse rate on a medical patient may require only simple processing. However, a failure to meet a processing deadline, such as decreasing plant power or sounding a medical alarm, can be literally fatal.
One example of a real time system is a multimedia system. Multimedia is increasingly recognized as an enabling technology with diverse applications from interactive training to medical diagnosis to control applications, for example. In the context of control applications, the term xe2x80x9cmultimediaxe2x80x9d implies a much broader scope than the traditional usage of the term that refers to audio, video and text. In the context of control applications, multimedia encompasses both the traditional multimedia data as well as image data and spectral data. Image data refers to still images, full-motion video, and graphics. Image data is obtained from sources such as video, X-ray, and scanning electron microscopy to name a few. Spectral data refers to sensor data. Spectral data is obtained from sources such as infrared, color, acoustic emission, ultrasound, microwave, laser, and optical sensors and devices, for example.
A multimedia-based control system imposes stringent requirements on a network. A key network requirement for multimedia-based control systems is that the underlying network must support real time tasks. Performance criteria for a network in such a control system are very different than those of a typical information network. Some basic performance criteria for a control network are (1) the guarantee of critical traffic, (2) the avoidance of priority inversion, and (3) the guarantee of deadlines. Priority inversion occurs when a lower priority task is allocated the resources before a higher priority task.
When scheduling real time tasks in a network, a priority or a deadline is associated with the task. For many real time tasks, failure to meet the deadline or failure to avoid priority inversion is considered a system fault. The priority or the deadline associated with a task is commonly specified globally at the user or application level. However, a kernel-level scheduling mechanism does not allow users or applications to exercise control over scheduling policies. As a result, user or application-level scheduling policies fail when kernel-level scheduling cannot enforce the same policy.
For these and other reasons, there is a need for a mechanism to guarantee correct scheduling order of real time tasks according to the user or application specified priorities or deadlines.
A network scheduler for real time applications is described. According to one aspect of the invention, a network scheduler acts as a proxy scheduler across different scheduling domains for the purpose of achieving correct deadline and priority based scheduling of network packets. An application specifies real time requirements in terms of deadlines or periodicities. An appropriate scheduling algorithm is applied based on the application task periodicities and deadlines. Simple primitives excercise control over operating system threads over scheduling domains to control their suspension and execution. The scheduling mechanism functions as a middleware system.
Another aspect of the invention is a scheduling method for an application distributed across a plurality of processing nodes. The scheduling method comprises a proxy scheduling mechanism at every node between the boundaries of a plurality of scheduling domains within a processing node. The scheduling method achieves overall end to end deadline and priority based scheduling for distributed real time applications running over a plurality of processing nodes with multiple scheduling domains.
The present invention is applicable to a variety of operating system platforms and middleware solutions for real time systems. The present invention allows user-level defined attributes, such as priorities and deadlines, and desirably overcomes constraints resulting from vendor specific operating system mechanisms that do not preserve such user specified attributes of real time behavior. The primitives of the invention allow various scheduling policies such as priority based or deadline based scheduling policies.
Still other and further embodiments, aspects and advantages of the invention will become apparent by reference to the drawings and by reading the following detailed description.